package leetcode_top;
import java.util.*;
import org.junit.*;

public class Ex29 {
    class Solution {
        public int divide(int dividend, int divisor) {
            long d1 = dividend, d2 = divisor;
            if (dividend < 0) d1 = -d1;
            if (divisor < 0) d2 = -d2;
            List<Long> times = new ArrayList<>();
            List<Long> divs = new ArrayList<>();
            long t = 1L;
            while (d2 <= dividend) {
                divs.add(d2);
                times.add(t);
                t += t;
                d2 += d2;
            }
            long res = 0;
            for (int i = divs.size() - 1; i >= 0; i--) {
                t = divs.get(i);
                if (t <= d1) {
                    d1 -= t;
                    res += times.get(i);
                }
            }
            if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) {
                res = -res;
            }
            if (res > 0 && res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
            if (res < 0 && res < Integer.MIN_VALUE) return Integer.MIN_VALUE;
            return (int) res;
        }

        public int divide1(int dividend, int divisor) {
            long d1 = dividend, d2 = divisor;
            if (dividend < 0) d1 = -d1;
            if (divisor < 0) d2 = -d2;
            List<Long> divs = new ArrayList<>();
            long t = 1L;
            while ( d2 <= dividend) {
                divs.add(d2);
                d2 += d2;
            }
            long res = 0;
            for (int i = divs.size() - 1; i >= 0; i--) {
                t = divs.get(i);
                if (t <= d1) {
                    d1 -= t;
                    res += (1L << i); //左移这个部分应有的倍数
                }
            }
            if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) {
                res = -res;
            }
            if (res > 0 && res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
            if (res < 0 && res < Integer.MIN_VALUE) return Integer.MIN_VALUE;
            return (int) res;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.divide(1000, 2));        
    }

    @Test
    public void test1() {
        Solution s = new Solution();
        System.out.println(s.divide(Integer.MAX_VALUE, -1));        
    }
}
